package zuo.algo.c10;

/**
 * 00:44-汉诺塔
 */
public class TowersOfHanoi {

    public static void exc1(int n) {
        process(n, "左", "右", "中");
    }

    /**
     * 该问题主要分为三步：
     *  1.把n-1个盘子由start移到other
     *  2.把第n个盘子由start移到end
     *  3.把n-1个盘子由other移到end
     */
    private static void process(int n, String start, String end, String other) {
        // 圆盘只有一个时，只需将其从A塔移到C塔
        if (n == 1) {
            System.out.println(start + "-->" + end);
            return;
        }
        // 递归，把start上编号1~n-1的圆盘移到other上，以end为辅助塔
        process(n - 1, start, other, end);
        // 把start上编号为n的圆盘移到end上
        System.out.println(start + "-->" + end);
        // 递归，把other上编号1~n-1的圆盘移到end上，以start为辅助塔
        process(n - 1, other, end, start);
    }

    public static void main(String[] args) {
        exc1(3);
    }
}
